package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         301,
		Discription: "删除最小的字符数，使括号组合有效",
		Level:       3,
		Labels: map[string]int{
			"层序遍历": 1,
			"哈希表":  1,
			"去重":  1,
		},
	})
}

func RemoveInvalidParentheses(s string) []string {
	//首先判断自己是不是合法的
	if isStrValid(s) {
		return []string{s}
	}

	res := make([]string, 0)

	//层序遍历，一次性判定相同长度下的字符串是否有匹配的
	q := []string{s}
	for len(q) != 0 {
		nextStateMap := make(map[string]bool, 0)
		length := len(q)
		hasMatch := false
		//循环里的字符串都是同一长度
		for i := 0; i < length; i++ {
			tempStr := q[i]
			if isStrValid(tempStr) {
				hasMatch = true
				res = append(res, tempStr)
			}

			if !hasMatch && len(tempStr) > 1 {
				for j := 0; j < len(tempStr); j++ {
					nextStr := tempStr[:j] + tempStr[j+1:]
					if !nextStateMap[nextStr] {
						q = append(q, nextStr)
						nextStateMap[nextStr] = true
					}
				}
			}
		}

		//如果当前长度有匹配的了，就不需要再减少字符进入下一层遍历了
		if hasMatch {
			break
		}
		q = q[length:]
	}

	if len(res) == 0 {
		return []string{""}
	}

	return res
}

func isStrValid(str string) bool {
	s := 0
	for i := range str {
		if str[i] == '(' {
			s++
		} else if str[i] == ')' {
			s--
			if s < 0 {
				return false
			}
		}
	}

	//注意s最终要为0
	return s == 0
}